//按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 
//
// n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 
//
// 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。 
//
// 
// 
// 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。 
// 
// 
//
// 
//
// 示例 1： 
// 
// 
//输入：n = 4
//输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
//解释：如上图所示，4 皇后问题存在两个不同的解法。
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：[["Q"]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 9 
// 
//
// Related Topics 数组 回溯 👍 1999 👎 0


package com.tyrone.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ScheduledExecutorService;

public class NQueens {
    public static void main(String[] args) {
        Solution solution = new NQueens().new Solution();
//        solution.solveNQueens(4);
//        [[".Q..","...Q","Q...","..Q."]
        char[][] arr = new char[][]{
                {'.', 'Q', '.', '.'},
                {'.', '.', '.', 'Q'},
                {'Q', '.', '.', '.'},
                {'.', '.', 'Q', '.'}
        };
        boolean check = solution.check(arr);
        System.out.println(check);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 我需要不断模拟棋子摆放顺序（遍历解空间），如果满足就加入
         * 对于n皇后，而言 每一行只能是只有个没一也只能有一个。
         *
         * @param n
         * @return
         */
        public List<List<String>> solveNQueens(int n) {
            List<List<String>> result = new ArrayList<>();
            char[][] arr = new char[n][n];
            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < arr[0].length; j++) {
                    arr[i][j] = '.';
                }
            }
            dfs(arr, 0, new ArrayList<>(), result);
            return result;
        }

        private void dfs(char[][] arr, int i, List<String> list, List<List<String>> result) {
            int n = arr.length;
            /**
             * 满足结束条件
             */
            if (list.size() == n) {
                result.add(new ArrayList<>(list));
                return;
            }
            for (int k = 0; k < n; k++) {
                /**
                 * 现在的解法超时了 我的解决是
                 * 1.提前判断当前位置能不能放置
                 * 2.dfs有多余的变量可以去掉
                 * 3.判断函数太复杂
                 */
//                arr[i][k] = 'Q';
//                if (doCheck(arr,i,k)){
//                    list.add(new String(arr[i])); //当前层的第i个放置皇后
//                    dfs(arr, i + 1,list, result);
//                    list.remove(list.size() - 1);
//                }
//                arr[i][k] = '.';
                /**
                 * 现在优化过后的算法
                 * 提前判断放位置能不能 并且优化 判断函数
                 */
                if (!isValid(arr, i, k)) continue;
                arr[i][k] = 'Q';
                list.add(new String(arr[i])); //当前层的第i个放置皇后
                dfs(arr, i + 1, list, result);
                list.remove(list.size() - 1);
                arr[i][k] = '.';
            }
        }

        /**
         * 他相比于下面的判断到底优化在哪里？
         * 1.省略行的对判断，因为每一次操作都是每一行的从头开始的
         * 2.斜线的判断不用考虑当前点下面的 只要之前的位置已经有皇后了，就说明当前的位置一定不能放。
         *
         *
         * @param board
         * @param row
         * @param col
         * @return
         */
        private boolean isValid(char[][] board, int row, int col) {
            //判断竖着
            for (int i = 0; i < row; i++)
                if (board[i][col] == 'Q') return false;
            //判断\方向左上角
            for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
                if (board[i][j] == 'Q') return false;
            // 判断/ 方向右上角
            for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++)
                if (board[i][j] == 'Q') return false;
            return true;
        }

        /**
         * 假设现在填充完了，需要判断当前的arr[]是不是有问题
         *
         * @param arr
         * @return
         */
        boolean check(char[][] arr) {
            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < arr[0].length; j++) {
                    if (arr[i][j] == 'Q') {
                        if (!doCheck(arr, i, j)) return false;
                    }
                }
            }
            return true;
        }

        boolean doCheck(char[][] arr, int i, int j) {
            int n = arr.length;
            //检查横线
            for (int k = 0; k < n; k++) {
                if (k != j && arr[i][k] == 'Q') return false;
            }
            //检查竖线
            for (int k = 0; k < n; k++) {
                if (k != i && arr[k][j] == 'Q') return false;
            }
            //检查‘/’线
            int k = i;
            int l = j;
            while (k < n && l >= 0) {
                if (arr[k][l] == 'Q' && k != i && l != j) return false;
                k++;
                l--;
            }
            k = i;
            l = j;
            while (l < n && k >= 0) {
                if (arr[k][l] == 'Q' && k != i && l != j) return false;
                k--;
                l++;
            }
            //检查'\'线
            k = i;
            l = j;
            while (k < n && l < n) {
                if (arr[k][l] == 'Q' && k != i && l != j) return false;
                k++;
                l++;
            }
            k = i;
            l = j;
            while (l >= 0 && k >= 0) {
                if (arr[k][j] == 'Q' && k != i && l != j) return false;
                k--;
                l--;
            }
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}